package leetcode101.tree;

/**
 * @author Synhard
 * @version 1.0
 * @class Code27
 * @description 897. 递增顺序搜索树
 * 给你一棵二叉搜索树，请你 按中序遍历 将其重新排列为一棵递增顺序搜索树，
 * 使树中最左边的节点成为树的根节点，并且每个节点没有左子节点，只有一个右子节点。
 *
 *
 * 示例 1：
 *
 *
 * 输入：root = [5,3,6,2,4,null,8,1,null,null,null,7,9]
 * 输出：[1,null,2,null,3,null,4,null,5,null,6,null,7,null,8,null,9]
 * 示例 2：
 *
 *
 * 输入：root = [5,1,7]
 * 输出：[1,null,5,null,7]
 *
 * @tel 13001321080
 * @email 823436512@qq.com
 * @date 2021-06-29 7:44
 */
public class Code27 {
    public static void main(String[] args) {

    }

    public TreeNode increasingBST(TreeNode root) {
        if (root == null) {
            return null;
        }
        TreeNode left = increasingBST(root.left);
        if (left != null) {
            TreeNode temp = left;
            while (temp.right != null) {
                temp = temp.right;
            }
            temp.right = root;
            root.left = null;
            root.right = increasingBST(root.right);
            return left;
        } else {
            root.right = increasingBST(root.right);
            return root;
        }
    }
}
